import java.util.ArrayList;


public class Algorithm {
	
	public Algorithm() {
		
	}
	
	/*
	 * Elimina i simboli che non generano word
	 * Data una grammatica ne genera una equivalente dove VN' include solo i simboli appartenenti a VT*
	 * e P' include solo le produzioni i cui simboli appartengono a VT U VN'
	 */
	public static Grammar FromBelowProcedure(Grammar G){
		
		Grammar g= new Grammar();
		ArrayList<String> vn = new ArrayList<String>();
		Productions p= new Productions();
		ArrayList<String> VN= G.getVN();
		ArrayList<String> union= new ArrayList<String>();
		union.addAll(G.getVT());
		Productions P= G.getP();
		
		vn.clear();
		
		for(String A : VN){
			
			if(P.isPresent(A) && !vn.contains(A)) {
				
				ArrayList<String> lhs= P.getProductionByKey(A).getLHS();
				for(String a : lhs){
					
					if(union.contains(a)){
						
						vn.add(A);//VN'
						union.add(A);//VT U VN'
						p.addProduction(A, a);
					}
				}
			}
		}
			
		g.setP(p);
		g.setVN(vn);
		g.setVT(G.getVT());
		g.setS(G.getS());
		
		return g;
	}
	
	//Elimina i simboli che non sono raggiungibili dal simbolo iniziale
	public static Grammar FromAboveProcedure(Grammar G){
		
		Grammar g= new Grammar();
		ArrayList<String> vt= new ArrayList<String>();
		ArrayList<String> vn= new ArrayList<String>();
		String S= G.getS();
		ArrayList<String> VN= G.getVN();
		ArrayList<String> VT= G.getVT();
		ArrayList<String> union= VN;
		Productions P= G.getP();
		union.addAll(VT);
		union= vn;
		union.addAll(vt);
		Productions p= new Productions();
		
		vt.clear();
		vn.add(S);
		
		for(String A : VN){
			
			if(P.isPresent(A) && !vn.contains(A)) {
				
				ArrayList<String> lhs= P.getProductionByKey(A).getLHS();
				
				for(String tmp : lhs){
					
					for(char c : tmp.toCharArray()){
							
							if(Character.isUpperCase(c) && VN.contains(Character.toString(c))){
								
								vn.add(Character.toString(c));
							}
							else if(Character.isLowerCase(c) && VT.contains(Character.toString(c))){
								
								vt.add(Character.toString(c));
							}
					}
				}
			}
		}
		
		for(String a : vn){
			
			ArrayList<String> lhs= P.getProductionByKey(a).getLHS();
			
			for(String tmp : lhs){
				
				for(char c : tmp.toCharArray()){
						
						if(Character.isUpperCase(c) && VN.contains(Character.toString(c))){
							
							p.addProduction(a, tmp);
						}
						else if(Character.isLowerCase(c) && VT.contains(Character.toString(c))){

							p.addProduction(a, tmp);
						}
				}
			}
		}
		
		g.setP(p);
		g.setS(S);
		g.setVN(vn);
		g.setVT(vt);
		
		return g;
	}
	
	//Elimina le Epsilon-productions
	public static Grammar EliminateEpsilonProductions(Grammar G){
		
		ArrayList<String> nullable= new ArrayList<String>();
		ArrayList<String> VN= G.getVN();
		ArrayList<String> VT= G.getVT();
		Productions P= G.getP();
		Productions originalP= G.getP();
		String epsilon= "e", S= G.getS();
		ArrayList<String> viewed= new ArrayList<String>();
		
		nullable.clear();
		
		/*
		 * costruisco l'insieme di elementi nullable
		 * step 1 di pagina 112 libro arancione
		 */
		for(String A : VN){
			
			if(Utility.isNullable(P, A, nullable, viewed)) nullable.add(A);
		}
		/*System.out.println("===========================================");
		for(String s : nullable){
			
			System.out.print(s+"-");
		}
		System.out.println("");
		System.out.println("===========================================");*/
		//-----
		
		//step 3 di pagina 112 libro arancione
		for(String A : P.getKeys()){

			ArrayList<String> lhs= P.getProductionByKey(A).getLHS();
			for(String tmp : lhs){
				
				char[] production= tmp.toCharArray();
				for(char c : production){
					
					if(nullable.contains(Character.toString(c)) && !VN.contains(Character.toString(c))) 
						Character.toString(c).replace(c, epsilon.charAt(0));
				}
			}
		}
		
		//step 4 pagina 112 libro arancione
		ArrayList<String> key= P.getKeys();
		for(String A : key){
			
			Production tmpLHS= P.getProductionByKey(A);			
			ArrayList<String> lhs= tmpLHS.getLHS();
			for(int i=0; i<lhs.size(); i++){
				
				String tmp= lhs.get(i);
				if(tmp.equals(epsilon)) {
					
					tmpLHS.removeProduction(i);
					if(tmpLHS.noMoreProductions()) P.removeAllProductionByKey(A);
				}
			}
		}
		
		//step 2 di pagina 112 libro arancione
		if(nullable.contains(S)) P.addProduction(S, epsilon);
		
		//creo le combinazioni possibili di non terminali che servono a rendere la grammatica equivalente a quella data
		for(Production p : P.getLHS()){
			
			ArrayList<String> tmpLHS= p.getLHScompact();
			ArrayList<String> support= new ArrayList<String>();
			for(String s : tmpLHS){
					
				if(Utility.isAllNonTerminal(s)){
						
					support= Utility.combine(s);
					System.out.println("combine s= "+s);
					for(String d : support) System.out.println("d= "+d);
					p.replaceLHS(s, support);
				}
			}
		}
		nullable.clear();
		for(String A : VN){
			
			if(Utility.isNullable(P, A, nullable, viewed)) nullable.add(A);
		}
		
		//controllo se non sono nullabili li tieni
		
		System.out.println("Prod= "+G.getP().getAllProduction());
		
		Grammar g= new Grammar(VN, VT, P, S);
		
		return g;
	}
	
	public static void EliminateUnitProductions(Grammar G){
		
		FIFO U= new FIFO();
		ArrayList<String> VN= G.getVN();
		Productions P= G.getP();

		do{
		
			//step 1 pagina 113 libro arancione
			for(String A : P.getKeys()){
				
				//System.out.println("key= "+A);
				
				Production tmpLHS= P.getProductionByKey(A);			
				ArrayList<String> lhs= tmpLHS.getLHScompact();
				for(String tmp : lhs){
					
					System.out.println( "A= "+A+", tmp= "+tmp);
				
					if(Utility.isTrivialUnit(A, tmp, VN)) {
						
						tmpLHS.removeProduction(tmp);
						System.out.println("remove tmp= "+tmp);
						System.out.println("Production removed= "+P.getAllProduction());
					}
					if(Utility.isUnit(A, tmp, VN) && !U.getFIFO().contains(A+"->"+tmp)) {
						
						U.push(A, tmp);
						System.out.println("push "+A+"->"+tmp);
					}
				}
			}
			System.out.println("===============");
			for(String a : U.getFIFO()){
				
				System.out.println(a);
			}
			System.out.println("===============");
			
			//step 2 pagina 114 libro arancione
			if(!U.getFIFO().isEmpty()){
				
				String unit= U.pop();
				String Aunit= unit.substring(0, unit.indexOf("->"));
				String Bunit= unit.substring(unit.indexOf("->")+2);
				System.out.println("unit= "+unit);
				System.out.println("Aunit= "+Aunit);
				System.out.println("Bunit= "+Bunit);
	
				System.out.println("Production= "+P.getAllProduction());
				System.out.println("----------------------------------");
				
				if(P.isPresent(Bunit) && P.isPresent(Aunit)){
		
					Production tmpLHS= P.getProductionByKey(Bunit);			
					ArrayList<String> lhs= tmpLHS.getLHS();
					P.getProductionByKey(Aunit).replaceLHS(Bunit, lhs);
				}
			}
			/*System.out.println("++++++++++++++++");
			for(String f : P.getProductionByKey(Aunit).getLHS()){
				
				System.out.print(f);
			}
			System.out.println("");
			System.out.println("++++++++++++++++");*/

			System.out.println("Production end= "+P.getAllProduction());
		}
		while(!U.getFIFO().isEmpty());
	}
}
